﻿// 0916train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <queue>

using namespace std;

/*
 有一个总空间为100字节的堆，现要从中新申请一块内存
内存分配原则为优先紧接着前一块已使用内存分配空间
且最接近申请大小的空闲内存

输入描述
第1行是1个整数，表示期望申请的内存字节
第2到N行是用空格分割的两个整数，表示当前已分配的内存的情况，
每一行表示一块已分配的连续内存空间，每行的第1和第2个整数分别表示偏移地址和内存块大小，
如:0 1 3 2分别表示0偏移地址开始的1个字节和3偏移地址开始的2个字节已被分配，
其余内存空闲

输出描述
若申请成功，输出申请到内存的偏移；若申请失败，输出-1

输入
1
0 1
3 2
输出
1

堆中已使用的两块内存是偏移从0开始1字节和偏移从3开始的2字节，
空闲的两块内存是偏移从1开始2个字节和偏移从5开始的95个字节，
根据分配原则，新申请的内存应从1开始分配1个字节，所以输出移为1
 */
class Solution01
{
public:
    void getInterval(vector<vector<int>>& origin_vec)
    {
        for (auto&item:origin_vec)
        {
            int start = item[0], end = item[0] + item[1];
            interval_vec.push_back({ start,end });
        }

        //排序
        sort(interval_vec.begin(), interval_vec.end(), [](vector<int>&vec_1, vector<int>& vec_2)
            {
                return vec_1[0] < vec_2[0];
            });

        //getInterval
    }
    Solution01(vector<vector<int>>&origin_vec, int target_buffer_size)
    {
        getInterval(origin_vec);

        //判断是否重叠
        int interval_vec_size = interval_vec.size();

        if (interval_vec[0][0] < 0 || interval_vec[interval_vec_size-1][1]>100)
        {
            cout << -1;
            return;
        }

        for (int i=1; i<interval_vec_size; i++)
        {
            int last_end = interval_vec[i - 1][1];
            int curr_start = interval_vec[i][0];

            if (last_end>curr_start)
            {
                cout << -1;
                return;
            }
        }

        //塞进{-1,0}用于判断0-interval_vec[0][0]
        //塞进{100,101}判断interval_vec[interval_vec_size-1][1]-100部分
        vector<vector<int>>new_interval = { {-1,0} };
        for (auto&item:interval_vec)
        {
            new_interval.push_back(item);
        }
        new_interval.push_back({ 100,101 });
        interval_vec = new_interval;
        interval_vec_size = interval_vec.size();

        int min_buffer_size = 100;
        int res = -1;

        for (int i=1; i<interval_vec_size; i++)
        {
            int last_end = interval_vec[i - 1][1];
            int curr_start = interval_vec[i][0];

            int free_buffer = curr_start - last_end;
            if (free_buffer>=target_buffer_size && free_buffer< min_buffer_size)
            {
                min_buffer_size = free_buffer;
                res = last_end;
            }
        }

        cout << res;
	    //Solution01
    }
private:
    vector<vector<int>>interval_vec;
};


/*
 让我们来模拟一个消息队列的运作，有一个发布者和若干消费者，
 发布者会在给定的时刻向消息队列发送消息：
1. 若此时消息队列有消费者订阅，这个消息会被发送到订阅的消费者中优先级最高
（输入中消费者按优先级升序排列）的一个；
2. 若此时没有订阅的消费者，该消息被消息队列丢弃。

消费者则会在给定的时刻订阅消息队列或取消订阅。
1. 当消息发送和订阅发生在同一时刻时，先处理订阅操作，
即同一时刻订阅的消费者成为消息发送的候选。
2. 当消息发送和取消订阅发生在同一时刻时，先处理取消订阅操作，
即消息不会被发送到同一时刻取消订阅的消费者。

输入描述
输入为两行。
第一行为2N个正整数，代表发布者发送的N个消息的时刻和内容（为方便解折，消息内容也用正整数表示）。第一个数字是第一个消息的发送时刻，第二个数字是第一个消息的内容，以此类推。用例保证发送时刻不会重复，但注意消息并没有按照发送时刻排列。
第二行为2M个正整数，代表M个消费者订阅和取消订阅的时刻。
第一个数字是第一个消费者订阅的时刻，第二个数字是第一个消费者取消订阅的时刻，
以此类推。用例保证每个消费者的取消订阅时刻大于订阅时刻，消费者按优先级升序排列。
两行的数字都由空格分隔。N不超过100，M不超过10，每行的长度不超过1000字符。


输出描述
输出为M行，依次为M个消费者收到的消息内容，消息内容按收到的顺序排列，且由空格分隔；
若某个消费者没有收到任何消息，则对应的行输出-1

输入
2 22 1 11 4 44 5 55 3 33
1 7 2 3
输出
11 33 44 55
22

消息11在1时刻到达，此时只有第一个消费者订阅，消息发送给它；
消息22在2时刻到达，此时两个消费者都订阅了，消息发送给优先级最高的第二个消费者；
消息33在3时刻到达，此时只有第一个消费者订阅，消息发送给它；

消费者按优先级升序排列，排在后面的优先级大
依次为M个消费者收到的消息内容
 */
class Solution02
{
public:
    struct Node
    {
        int time, val;
        Node() = default;
        Node(int time, int val) :time(time), val(val) {};

        bool operator<(const Node&other)const
        {
            return time < other.time;
        }
    };
    void initData(vector<int>& vec_pro, vector<int>&vec_rec)
    {
        int v_pro_size = vec_pro.size();
        for (int i=0; i< v_pro_size -1;i+=2)
        {
            Node node(vec_pro[i], vec_pro[i + 1]);
            produce_vec.push_back(node);
        }

        sort(produce_vec.begin(), produce_vec.end());

        int v_rec_size = vec_rec.size();
        for (int i=0; i<v_rec_size-1;i+=2)
        {
            vector<int>interval(2);
            interval[0] = vec_rec[i];
            interval[1] = vec_rec[i + 1];
            receive_vec.push_back(interval);
        }
        //优先级大的排前面
        reverse(receive_vec.begin(), receive_vec.end());

        result.resize(receive_vec.size());
        //initData
    }
    Solution02(vector<int>& vec_pro, vector<int>& vec_rec)
    {
        initData(vec_pro, vec_rec);
        for (auto&node:produce_vec)
        {
            int receive_vec_size = receive_vec.size();
            for (int i=0; i< receive_vec_size; i++)
            {
                vector<int>interval = receive_vec[i];
                int start = interval[0], end = interval[1];

                //同一时刻订阅 可以发
                //同一时刻取消 发不了
                if (node.time>=start && node.time<end)
                {
                    result[i].push_back(node.val);
                    break; //找到消费者，退出
                }
            } //寻找receive
        }
        
        

        //保持原来的顺序
        reverse(result.begin(), result.end());

        int result_size = result.size();
        for (int level=0; level< result_size; level++)
        {
            vector<int>level_vec = result[level];

            //某个消费者没有收到任何消息,输出-1
            if (level_vec.empty())
            {
                cout << -1;
                cout << '\n';
                continue;
            }

            int level_size = level_vec.size();
            for (int i=0;i< level_size; i++)
            {
                cout << level_vec[i];
                if (i!=level_size-1)
                {
                    cout << ' ';
                }
            }

            if (level!=result_size-1)
            {
                cout << '\n';
            }
        }

	    //Solution02
    }
private:
    vector<vector<int>>result;
    vector<Node>produce_vec;
    vector<vector<int>>receive_vec;
};


/*
 有一个特异性的双端队列，该队列可以从头部或尾部添加数据，但是只能从头部移出数据。
小A依次执行2n个指令往队列中添加数据和移出数据。
其中n个指令是添加数据（可能从头部添加、也可能从尾部添加），依次添加1到n；
n个指令是移出数据。

现在要求移除数据的顺序为1到n。
为了满足最后输出的要求，小A可以在任何时候调整队列中数据的顺序。
请问 小A 最少需要调整几次才能够满足移除数据的顺序正好是1到n

输入描述
第一行一个数据n，表示数据的范围。
接下来的2n行，其中有n行为添加数据，指令为：
- head add x表示从头部添加数据 x，
- tail add x 表示从尾部添加数据 x，
另外 n 行为移出数据指令，指令为：remove 的形式，表示移出1个数据
所有的数据均合法。

输出描述
一个整数，表示 小A 要调整的最小次数。

输入
5
head add 1
tail add 2
remove
head add 3
tail add 4
head add 5
remove
remove
remove
remove

输出
1
 */
class Solution03
{
public:
    Solution03(vector<string>&order_vec)
    {
        int change_count = 0;
        int curr_num = 1;
        deque<int>exec_queue;
        for (auto&order_str:order_vec)
        {
            //依次添加1到n
            if (order_str=="remove")
            {
                int top = exec_queue.front();
                if (top!=curr_num)
                {
                    vector<int>sort_vec;

                    while (!exec_queue.empty())
                    {
                        sort_vec.push_back(exec_queue.front());
                        exec_queue.pop_front();
                    }
                    sort(sort_vec.begin(), sort_vec.end());
                    for (auto&num:sort_vec)
                    {
                        exec_queue.push_back(num);
                    }

                    change_count++;
                }
                curr_num++;
                exec_queue.pop_front();
                continue;
            }
            
            vector<string>item_v;
            stringstream order_sstream(order_str);
            string token;
            while (order_sstream>>token)
            {
                item_v.push_back(token);
            }

            int curr_num = stoi(item_v[2]);
            if (item_v[0]=="head")
            {
                exec_queue.push_front(curr_num);
            }
            else if (item_v[0] == "tail")
            {
                exec_queue.push_back(curr_num);
            }
        }

        cout << change_count;
        //Solution03
    }
};

class Solution13
{
public:
    Solution13(vector<vector<string>>&order_vec)
    {
        //队头加入，一定会乱序
        bool is_confuse = false;

        int change_count = 0;

        int queue_size = 0;
        for (auto&order_item:order_vec)
        {
            if (order_item[0]=="head")
            {
                if (queue_size != 0)
                {
                    is_confuse = true;
                }
                queue_size++;
            }
            else if (order_item[0] == "tail")
            {
                queue_size++;
            }
            else if (order_item[0]=="remove")
            {
	            if (is_confuse)
	            {
                    change_count += 1;
                    is_confuse = false;
	            }
                queue_size--;
            }

        }

        cout << change_count;

	    //Solution13
    }
};

int main()
{
	{
        int total;
        cin >> total;
        cin.ignore();
        vector<vector<string>>order_vec(total * 2);

        for (int i=0; i< total *2; i++)
        {
            vector<string>str_vec;
            string order_str;
            getline(cin, order_str);

            stringstream order_sstream(order_str);
            string token;
            while (order_sstream>>token)
            {
                str_vec.push_back(token);
            }
            order_vec[i] = str_vec;
        }

        Solution13 solu(order_vec);

        return 0;
	}
	{
/*
2 22 1 11 4 44 5 55 3 33
1 7 2 3
*/
        string produce_str;
        getline(cin, produce_str);

        vector<int>vec_pro;
        stringstream pro_sstream(produce_str);
        string token;
        while (pro_sstream>>token)
        {
            vec_pro.push_back(stoi(token));
        }

        vector<int>vec_rec;
        string receive_str;
        getline(cin, receive_str);
        stringstream rec_sstream(receive_str);
        while (rec_sstream>>token)
        {
            vec_rec.push_back(stoi(token));
        }

        Solution02 solu(vec_pro, vec_rec);

        return 0;
	}
    int target_buffer_size;
    cin >> target_buffer_size;
    cin.ignore();

    vector<vector<int>>origin_vec;

    string input;
    while (getline(cin,input))
    {
        if (input.empty())break;
        vector<int>item_v;
        stringstream oh_sstream(input);
        string token;
        while (oh_sstream>>token)
        {
            item_v.push_back(stoi(token));
        }
        origin_vec.push_back(item_v);
    }
    Solution01 solu(origin_vec, target_buffer_size);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
